/*
 * @lc app=leetcode.cn id=572 lang=cpp
 *
 *
 *
 */

// @lc code=start
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

struct TreeNode
{
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode* next;
  TreeNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};

class Solution
{
 public:
  TreeNode* GetNext(TreeNode* p)
  {
    if (nullptr == p) return nullptr;

    if (p->right)  // 有右子树时，下个结点就是它右子树的最左子结点
    {
      p = p->right;
      while (p->left != nullptr) p = p->left;
      return p;
    }
    else  //没有右子树时，下个结点就是父结点（当前结点为左孩子时）或者向上遍历，以遍历到的结点为其上节点的左孩子返回该上节点(这个节点的父节点)
    {
      while (p->next)
      {
        if (p->next->left == p)  // 若为父结点的左结点，则父结点就是下一个结点
        {
          return p->next;
        }
        else
        {
          p = p->next;  // 往上查找，直到当前结点为父结点的左结点
        }
      }

      return nullptr;
    }
  }
};
// @lc code=end
